import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author VernHe
 * @date 2021年06月08日 13:13
 */
public class Solution_0148 {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((ListNode)o1).val - ((ListNode)o2).val;
            }
        };
        PriorityQueue<ListNode> queue = new PriorityQueue(comparator);
        ListNode cur = head;
        // 初始化
        while (cur != null) {
            queue.add(cur);
            cur = cur.next;
        }
        ListNode newHead = new ListNode();
        ListNode prev;
        cur = newHead;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            prev = cur;
            cur = cur.next;
        }
        cur.next = null;
        return newHead.next;
    }
}
